package heap;


/**
 * 重点  新增加到尾部 重建堆          从下网上rebuildHeap()
 *      移除头部将最后一个放到data[0] 从上往下heapify(0)
 */
class 重做版 {
    public int lastStoneWeight(int[] stones) {
        MaxHeap maxHeap = new MaxHeap(stones);
        while(maxHeap.size() > 1) {
            int y = maxHeap.poll();
            int x = maxHeap.poll();
            if(y > x) {
                maxHeap.push(y - x);
            }
        }
        return maxHeap.size() == 1 ? maxHeap.poll() : 0;
    }

    private class MaxHeap{
        final int[] data;
        int tail;
        public MaxHeap(int[] data) {
            this.data = data;
            this.tail = data.length - 1;
            buildHeap();
        }

        private void heapify(int i) {
            int r = (i + 1) << 1;
            int l = r - 1;
            int max = i;
            if(r <= tail && data[max] < data[r]) max = r;
            if(l <= tail && data[max] < data[l]) max = l;
            if(max == i) return;
            swap(max, i);
            heapify(max);
        }

        private void buildHeap() {
            for(int i = ((this.tail + 1) >> 1) - 1; i >= 0; i--){
                heapify(i);
            }
        }

        private void swap(int p, int q) {
            int temp = data[p];
            data[p] = data[q];
            data[q] = temp;
        }

        public void push(int i) {
            data[++tail] = i;
            buildHeap();
        }

        public int poll() {
            int root = data[0];
            data[0] = data[tail--];
            heapify(0);
            return root;
        }

        public int size() {
            return tail + 1;
        }
    }
}
/**
 * 插入的基本思想很简单，你在堆的最后新加一个节点，再对这个新构成的二叉树数组（新增了一个元素的堆）进行建堆即可。
 * <p>
 * 删除也很简单，对于堆来讲删除就只能删除根节点，在堆里，你不能直接删除，你需要把堆尾元素剪切，复制到堆首，覆盖掉原来的堆首元素，然后还是再对这个新构成的二叉树数组（删掉一个元素的堆）进行建堆即可。
 * <p>
 * 堆排序  见删除  但是size 不减一：
 * <p>
 * 将堆顶元素与第size-1个元素交换。
 * 将其余的元素调整为最小堆
 * 重复1、2、3步hp->size-1次。
 */
public class 最后一块石头的重量_1046 {

    public int lastStoneWeight(int[] stones) {
        MaxHeap heap = new MaxHeap(stones);
        while (heap.heapSize > 1) {
            final int max = heap.pop();
            final int next = heap.pop();
            if (max - next != 0) {
                heap.push(max - next);
            }
        }
        return heap.heapSize == 0 ? 0 : heap.getRoot();
    }

    private class MaxHeap {
        int[] heapData;
        int heapSize;

        public MaxHeap(int[] heapData) {
            this.heapData = heapData;
            this.heapSize = heapData.length;
            buildHeap();
        }

        private void buildHeap() {
            // 这里用heapSize  不是用heapData.length  因为 push插入元素也会用到 push 的时候 heapSize改变了
            for (int i = heapSize / 2 - 1; i >= 0; i--) {
                heapify(i);
            }
        }

        private void heapify(int i) {
            //  << 1 等价于  * 2  不是 << 2  那就成了 * 4 了
            int rightChild = (i + 1) << 1;
            int leftChild = rightChild - 1;
            int max = i;
            if (rightChild < heapSize && heapData[rightChild] > heapData[max]) {
                max = rightChild;
            }
            if (leftChild < heapSize && heapData[leftChild] > heapData[max]) {
                max = leftChild;
            }
            if (max == i) {
                return;
            }
            swap(i, max);
            heapify(max);
        }

        private void swap(int root, int child) {
            int temp = heapData[root];
            heapData[root] = heapData[child];
            heapData[child] = temp;
        }

        public int pop() {
           /* System.out.println("before pop");
            for (int i : heapData) {
                System.out.print(i);
                System.out.print(" ");
            }
            System.out.println();*/

            int root = heapData[0];
            heapData[0] = heapData[heapSize - 1];
            heapSize--;
            heapify(0);

            /*System.out.println("after pop");
            for (int i =0; i< heapSize ; i ++  ) {
                System.out.print(heapData[i]);
                System.out.print(" ");
            }
            System.out.println();*/
            return root;
        }

        public void push(int newData) {
            assert heapSize < heapData.length - 1;
            /*System.out.println("before push");
            for (int i : heapData) {
                System.out.print(i);
                System.out.print(" ");
            }
            System.out.println();*/

            heapData[heapSize] = newData;
            // 注意  ++  和buildHeap的顺序  反了就重建错了
            heapSize++;
            buildHeap();
            /*System.out.println("after push");
            for (int i =0; i< heapSize ; i ++  ) {
                System.out.print(heapData[i]);
                System.out.print(" ");
            }
            System.out.println();*/

        }

        public int getRoot() {
            return heapData[0];
        }
    }


}
